Tree Data Structure is used to organise data in hierarchical manner.
In this video we discuss about:
node,root,leaf,child,parent,subtree,descendants,ancestors,degree and internal nodes.
This track of the course covers the topic "Trees".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Trees.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
Tree Data Structure is used to organise data in hierarchical manner.
In this video we discuss about:
node,root,leaf,child,parent,subtree,descendants,ancestors,degree and internal nodes.
In this video, we discuss applications of Trees:
In Binary Tree every node has at most two children.
In this video, we further discuss the implementation to represent a Binary Tree.
Codes:
Tree Traversal is basically going through every node(key) exactly once.
In this video we briefly discuss:
Types of Tree Traversal i.e. Breadth-First Search(BFS) and Depth First Search(DFS).
Inorder, preorder and postorder traversals.
Implementation of Inorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print inorder traversal of the Tree whose nodes are given.
Codes:
Implementation of Preorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Preorder traversal of the Tree whose nodes are given.
Codes:
Implementation of Postorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Postorder traversal of the Tree whose nodes are given.
Codes:
Height of Binary Tree is the number of nodes between the longest path from root to leaf node(including the root and leaf node).
In this video we discuss about a recursive function that takes root of the tree and returns the height of the Binary Tree.
Codes:
Nodes at distance k from the root are basically the nodes at (k+1)th level of the Binary Tree.
In this video, we discuss a function that takes root and k as a parameter, whose return type is void and is supposed to print the nodes at distance k from the root.
Codes:
Level order traversal of a tree is breadth first traversal of binary tree.
In this video we will discuss about a function that takes root as a parameter, doesn’t returns anything and prints the level order traversal in a single line.we implement this function using queue datastructure.
Codes:
In Level Order Traversal Line by Line, we print the nodes at each level separately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-1.
In method-1, we implement this function using a single loop.
Codes:
In Level Order Traversal Line by Line, we print the nodes at each level seperately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-2.
In method-2, we implement this function using nested loops.
Codes:
Size of Binary Tree is the total numbers of nodes present in that Tree.
In this video, we discuss a recursive function that takes root as a parameter and is supposed to return the size of the Tree whose nodes are given.
Codes:
Largest node(key) in a Tree is the maximum of the Tree.
In this video, we discuss a recursive function that takes the root of a binary Tree and returns the maximum of the Tree.
Codes:
To Print Left View of Binary Tree we need to print the leftmost node at every level of the Binary Tree.
In this video we discuss two methods to print left view of a given Binary Tree.In Method-1 we use Recursive method whereas in Method-2 we use the Iterative method approach by using queue datastructure.
Codes:
Children Sum Property is a property in which the sum of values of the left child and right child should be equal to the value of their node if both children are present. Else if only one child is present then the value of the child should be equal to its node value.
In this video, we discuss a recursive function that takes the root node as a parameter and returns TRUE if the Tree follows C.S.P. and FALSE if the Tree does not follow C.S.P.
Code:
In a Balanced Binary Tree for every node, the difference between heights of left subtree and right subtree should not be more than one.
In this video we discuss two solutions (one with time complexity of O(n^2) and another with time complexity of O(n) ) to check whether a Tree is Balanced or not.
Codes:
Maximum Width of Binary tree is the maximum number of nodes present in a level of the Tree.
In this video, we discuss a function that takes the root of a Binary Tree and returns the maximum width of the Binary Tree.
Hint:- we use level order traversal line by line logic to find maximum width of the Binary Tree.
Codes:
In this video we discuss:
Inorder conversion of Binary Tree to Doubly Linked List.
A function that takes root of a Binary Tree and converts it into a Doubly linked list.
Hint:- we need to do the inorder traversal of the Tree and while doing inorder traversal we can simply maintain a previous pointer or reference of the previously traversed node. And change right child of the previous node to current node and left child of current node as previous.
Codes:
This video discusses the Construction of a Binary Tree from Inorder and Preorder traversal.
Codes:
This video discusses the method of Tree Traversal in Spiral Form.
Codes:
Three method of finding diameter of a Binary Tree are discussed.
Codes:
Introduction to LCA (Lowest Common Ancestor) problem and a O(n) solution to the problem.
Codes:
An efficient solution is discussed in this video. The solution does only one traversal of binary tree, but assumes that both keys exist in the binary tree.
Codes:
We are given a binary tree and a leaf node, we need to find time to burn the Binary Tree if we burn the given leaf at 0-th second.
Codes:
Given a binary tree, our task is to count toal nodes. Two methods are discussed here, naive method which is O(n). And an efficient method which is O(Log n * Log n)
Codes:
This video talks about serialize and deserialize a binary tree. It discusses preorder traversal based approach.
Codes:
The video discisses stack based inorder traversal.
A O(n) extra space and O(n) time solution is discussed.
A O(h) extra space and O(n) time solution is discussed.
A Tree is a non-linear data structure where each node is connected to a number of nodes with the help of pointers or references.

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child, or 2 child nodes.

L <= 2l-1 [From Point 1]
l = Log2L + 1
where l is the minimum number of levels.
L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children
In a Full Binary, the number of leaf nodes is number of internal nodes plus 1.
A Perfect Binary Tree of height h (where height is the number of nodes on the path from the root to leaf) has 2h – 1 node.![]()

Algorithm Inorder(tree)Example: Inorder traversal for the above-given tree is 4 2 5 1 3.
1. Traverse the left subtree, i.e.,
call Inorder(left->subtree)
2. Visit the root.
3. Traverse the right subtree, i.e.,
call Inorder(right->subtree)
Algorithm Preorder(tree)Example: Preorder traversal for the above-given tree is 1 2 4 5 3.
1. Visit the root.
2. Traverse the left subtree, i.e.,
call Preorder(left-subtree)
3. Traverse the right subtree, i.e.,
call Preorder(right-subtree)
Algorithm Postorder(tree)Example: Postorder traversal for the above-given Tree is 4 5 2 3 1.
1. Traverse the left subtree, i.e.,
call Postorder(left-subtree)
2. Traverse the right subtree, i.e.,
call Postorder(right-subtree)
3. Visit the root.
Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1


1 2 3 4 5

Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8
Delete 10 in below tree
Output :![]()
Delete 20 in below tree
Output :

Inorder traversal before Deletion: 7 11 12 10 15 9 8
Inorder traversal after Deletion: 7 8 12 10 15 9
The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Finding LCA
Method 1: The simplest method of finding LCA of two nodes in a Binary Tree is to observe that the LCA of the given nodes will be the last common node in the paths from the root node to the given nodes.LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2
LCA(4, 5) = 2nLCA(4, 6) = 1nLCA(3, 4) = 1nLCA(2, 4) = 2

1 + height of left subtree of nd + height of right subtree of nd
Diameter = maximum(lDiameter, rDiameter, 1 + lHeight + rHeight)
Where,
lDiameter = Diameter of left subtree
rDiameter = Diameter of right subtree
lHeight = Height of left subtree
rHeight = Height of right subtree
Diameter of the given binary tree is 4
Consider the Below Binary Tree:
Left View of above Tree will be: 1, 2, 4
Right View of above Tree will be: 1, 3, 7
Top View of above Tree will be: 4, 2, 1, 3, 7
Bottom View of above Tree will be: 4, 5, 6, 7
Solution - The idea is to do something similar to vertical Order Traversal. Like vertical Order Traversal, we need to put nodes of same horizontal distance together. We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. Hashing is used to check if a node at a given horizontal distance is seen or not.
Top view of the above binary tree is
4 2 1 3 7
Top view of the above binary tree is
2 1 3 6
// function should print the topView of
// the binary tree
void topview(Node* root)
{
if(root==NULL)
return;
queue < Node* > q
map < int,int > m
int hd=0
root->hd=hd
// push node and horizontal distance to queue
q.push(root);
while(!q.empty())
{
hd=root->hd
// check whether node at hd distance seen or not
if(m.find(hd)==false)
m[hd]=root->data
if(root->left)
{
root->left->hd=hd-1
q.push(root->left)
}
if(root->right)
{
root->right->hd=hd+1
q.push(root->right)
}
q.pop()
root=q.front()
}
for(it=m.begin();it!=m.end();it++)
{
print(it->second)
}
}

int diameter(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0
if(root == NULL)
{
*height = 0
return 0 /* diameter is also 0 */
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameter(root->left, &lh)
rdiameter = diameter(root->right, &rh)
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1
return max(lh + rh + 1, max(ldiameter, rdiameter))
}
// function to convert binary tree to it's mirror
void mirror(struct Node* node)
{
if (node == NULL)
return
else
{
struct Node* temp
/* Recur for subtrees */
mirror(node->left)
mirror(node->right)
/* swap the pointers in this node */
temp = node->left
node->left = node->right
node->right = temp
}
}
Solution - The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
// Base case
if (root == NULL)
return
// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL
// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root->left, head)
// Now convert this node
if (prev == NULL)
*head = root
else
{
root->left = prev
prev->right = root
}
prev = root
// Finally convert right subtree
BinaryTree2DoubleLinkedList(root->right, head)
}
A | Every binary tree is either complete or full. |
B | Every complete binary tree is also a full binary tree. |
C | Every full binary tree is also a complete binary tree. |
D | No binary tree is both complete and full. |
E | None of the above |